package 动态规划;

public class 判断子序列 {

    //动态规划预处理数组.贪心加双指针就不写了
    public static boolean isSubsequence(String s, String t) {
        int n = s.length();
        int m = t.length();
        //dp[i][j]表示i下标(包括i)之后j字符第一次出现的位置
        int[][] dp = new int[m+1][26];
        for (int i = 0; i < 26; i++) {
            //初始化dp,从后往前推,数值为m代表不存在
            dp[m][i] = m;
        }
        for (int i = m -1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (j == t.charAt(i) - 'a'){
                    dp[i][j] = i;
                }else {
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        int index = 0;
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            int j = dp[index][c];
            if (j==m){
                return false;
            }
            index = j+1;
        }
        return true;
    }

    public static void main(String[] args) {
        String s ="abc";
        String t = "ahbgdc";
        System.out.println(isSubsequence(s,t));
    }
}
